Online Judge►UVa

[UVa] 12176 - Bring Your Own Horse

題意

騎士必須從住的城堡到比賽場地，而他們每經過一個點就得花上一天且不論距離多遠，但他們的馬相當固執，一天內可能累積走到某個距離就不走了，因此他們寧可選擇走較多天但點與點距離較短的路來避免馬罷工，請輸出這條路中最長的點與點距離。

解法

產生最小生成樹後，兩點之間的邊即為題目所求的路，再對起點做DFS找到終點即可。

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <fstream>
using namespace std;
struct Node{
	int length , index1 , index2 ;
	Node(int x , int y , int l){
		index1 = x , index2 = y , length = l ;
	}
};
int Element[3005] ;
int Size[3005] ;
int maxEdge ;
vector<Node*> edge ;
vector<vector<Node* > > tree ;
vector<bool> visit ;
bool dfs(int x , int y ){
	if ( x == y )
		return true ;
	bool result ;
	for ( int i = 0 ; i < tree[x].size() ; i ++ ){
		if ( visit[tree[x][i]->index2] == false ){
			visit[tree[x][i]->index2] = true ;
			result = dfs(tree[x][i]->index2,y) ;
			visit[tree[x][i]->index2] = false ;
			if ( result == true ){
				maxEdge = max(maxEdge,tree[x][i]->length) ;
				return true ;
			}
		}
	}
	return false ;
}
int findElement(int x){
	while ( x != Element[x]){
		Element[x] = Element[Element[x]];
		x = Element[x];
	}
	return x ;
}
bool isConnected(int x ,int y){
	return findElement(x) == findElement(y) ;
}
void unionElement(int x , int y){
	int r_x = findElement(x);
	int r_y = findElement(y);
	if (r_x == r_y)
		return ;
	else
	{
		if (Size[r_x] < Size[r_y])
		{
			Element[r_x] = r_y ;
			Size[r_y] += Size[r_x] ;
		}
		else
		{
			Element[r_y] = r_x ;
			Size[r_x] += Size[r_y] ;
		}
	}
}
void initialize(int x){
	for ( int i = 1 ; i < x ; i ++ ){
		Element[i] = i ;
		Size[i] = 1 ;
	}
}
bool compare(const Node *n1,const Node *n2)
{
   return (n1->length)<(n2->length);
}
int main()
{
	int T , N , R , Q , a , b , l ;
	cin >> T ;
	tree.resize(3005) ;
	visit.resize(3005) ;
	for ( int t = 0 ; t < T  ; t ++ ){
		cin >> N >> R ;
		tree.clear();
		edge.clear();
		initialize(N+1) ;
		tree.resize(N+1) ;
		Node* node = new Node(0,0,0) ;
		for ( int r = 0 ; r < R ; r ++ ){
			cin >> a >> b >> l ;
			node = new Node(a,b,l) ;
			edge.push_back(node) ;
		}
		sort(edge.begin(),edge.end(),compare) ;
		int edgeCount = 0 ;
		for ( int i = 0 ; i < edge.size() && edgeCount < N ; i ++ ){
			if( isConnected(edge[i]->index1,edge[i]->index2) == false ){
				unionElement(edge[i]->index1,edge[i]->index2) ;
				tree[edge[i]->index1].push_back(edge[i]);
				node = new Node(edge[i]->index2,edge[i]->index1,edge[i]->length) ;
				tree[edge[i]->index2].push_back(node);
				edgeCount ++ ;
			}
		}
		cout << "Case " << t + 1 << endl ;
		cin >> Q ;
		int index1 , index2 ;
		for ( int q = 0 ; q < Q ; q ++ ){
			cin >> index1 >> index2 ;
			for ( int i = 1 ; i <= N ; i ++ )
				visit[i] = false ;
			visit[index1] = true ;
			maxEdge = 0 ;
			dfs(index1,index2) ;
			cout << maxEdge << endl ;
		}
		cout << endl ;
	}
	return 0;
}